import java.util.Scanner;

/**
 * @description：单链表实现 LRU
 * @author: yangyahui01
 * @date: 12/30/24 5:03 PM
 */
public class 单链表实现LRU淘汰策略 {

    public static void main(String[] args) {

        LruLinkedList lruLinkedList = new LruLinkedList();
        Scanner sc = new Scanner(System.in);
        while (true) {
            lruLinkedList.addElement(sc.nextInt());
            lruLinkedList.printAll();
        }



    }


    static class LruLinkedList<T> {
        private ListNode node;

        private int capacity;

        private int length;

        public LruLinkedList() {
            this.node = new ListNode(-1);
            this.capacity = 3;
            this.length = 0;
        }

        public LruLinkedList(int capacity) {
            this.node = new ListNode(-1);
            this.capacity = capacity;
            this.length = 0;
        }

        private void printAll() {

            ListNode tNode = node.next;

            while (tNode != null) {
                System.out.print(tNode.val + " ");
                tNode = tNode.next;
            }
            System.out.println();
        }

        /**
         * 向链表插入元素
         *
         * @param value 元素
         */
        public void addElement(int value) {

            ListNode preNode = findPreNode(value);

            if (preNode != null) {

                deleteElemOptim(preNode);
                intsertElemAtBegin(value);

            } else {
                if (length >= this.capacity) {
                    //删除尾结点
                    deleteElemAtEnd();
                }
                intsertElemAtBegin(value);
            }


        }

        private void deleteElemAtEnd() {

            ListNode p = node;
            if (p.next == null) {
                return;
            }

            while (p.next.next != null){
                p = p.next;
            }

            p.next = null;

            length--;
        }

        /**
         * 插入到头节点，是插入到哨兵节点的后一个
         * @param value
         */
        private void intsertElemAtBegin(int value) {

            ListNode listNode = new ListNode(value);

            listNode.next = node.next;

            node.next = listNode;


            length++;

        }

        /**
         * 删除原来的
         *
         * @param preNode
         */
        private void deleteElemOptim(ListNode preNode) {

            ListNode temp = preNode.next;

            preNode.next = temp.next;

            temp = null;

            length--;


        }

        /**
         * 找到目标元素的前一个节点
         *
         * @param value
         * @return
         */
        public ListNode findPreNode(int value) {

            ListNode p = node;

            while (p.next != null) {
                if (p.next.val == value) {
                    return p;
                }
                p = p.next;
            }

            return null;
        }


    }
}
